//
// Created by littlebear on 2022/5/21.
//

#include <iostream>
#include <vector>

#define INF 0x3f3f3f3f
#define maxn 100

using namespace std;

struct edge {
    int v, w; // v: 终点， w: 权重
};

int n, m; // n: 顶点数， m: 边数
int dis[maxn], vis[maxn];
vector<edge> graph[maxn];

void dijkstra(int s) {
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, min = INF;
        // 找到未访问的、距离最小的顶点
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < min) {
                u = j;
                min = dis[j];
            }
        }
        if (u == -1) break;
        vis[u] = true;
        // 更新距离（松弛）
        for (int j = 0; j < graph[u].size(); j++) {
            int v = graph[u][j].v;
            int w = graph[u][j].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w; // u: 起点， v: 终点， w: 权重
        cin >> u >> v >> w;
        graph[u].push_back((edge) {v, w});
    }
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = false;
    }
    // 执行dijkstra算法，寻找从s到其他顶点的最短路径
    dijkstra(1);
    for (int i = 1; i <= n; i++) {
        if (dis[i] == INF) printf("node 1 to %d: weight INF\n", i);
        else printf("node 1 to %d: minimum weight is %d\n", i, dis[i]);
    }
    return 0;
}